import java.util.*;

/**
 * 该类用于实现DFA最小化  输入：DFAGraph 输出：DFAGraph
 * 思路：1.DFAGraph->DFAMatrix
 *      2.划分终态集和非终态集
 *      3.循环进行分组
 *      4.重命名
 *      5.DFAMatrix->DFAGraph
 */
public class MinDFA {
    /**
     * 根据状态转换字符找到行坐标
     * @param name
     * @param access 状态转换集
     * @return 行坐标
     */
    public static int find_col_position(Character name, List<Character> access){
        int position=-1;
        for (int i = 0; i < access.size(); i++) {
            if(access.get(i)==name){
                return i;
            }
        }
        return position;
    }

    /**
     * 根据状态字符找到列坐标
     * @param state
     * @param states
     * @return 列坐标
     */
    public static int find_row_position(State state, List<State> states){
        int position=-1;
        for (int i = 0; i < states.size(); i++) {
            if(states.get(i).name==state.name){
                return i;
            }
        }
        return position;
    }
    /**
     * DFAGraph->DFAMatrix
     * @param dfaGraph
     * @return
     */
    public static DFAMatrix DFAGraph_to_DFAMatrix(DFAGraph dfaGraph){
        DFAMatrix dfaMatrix=new DFAMatrix(new ArrayList<State>(), new ArrayList<Character>(), 0, 0, new State(), new ArrayList<State>());
        //开始状态与结束状态相同
        dfaMatrix.startState=dfaGraph.startState;
        dfaMatrix.endStateList=dfaGraph.endStateList;
        //边数
        dfaMatrix.arcCount=dfaGraph.arcCount;
        //行头=状态转换集
        dfaMatrix.access=dfaGraph.access;

        //列头为Graph中的顶点
        //遍历Graph的边，转为List(去重)
        for (int i = 0; i < dfaGraph.arcCount; i++) {
            dfaMatrix.states.add(dfaGraph.arcCollection[i].start);
            dfaMatrix.states.add(dfaGraph.arcCollection[i].end);
        }
        char[] states=new char[dfaMatrix.states.size()];
        for (int i = 0; i < dfaMatrix.states.size(); i++) {
            states[i]=dfaMatrix.states.get(i).name;
        }
        for (int i = 0; i < states.length; i++) {
            for (int j = i+1; j < states.length; j++) {
                if(states[i]==states[j]){
                    states[j]='#';
                }
            }
        }
        dfaMatrix.states.clear();
        for (int i = 0; i < states.length; i++) {
            if(states[i]!='#'){
                dfaMatrix.states.add(new State(states[i]));
            }
        }
        // System.out.println(dfaMatrix.states.toString());
        int mcol=dfaGraph.access.size();
        int mrow=dfaMatrix.states.size();
        dfaMatrix.accessMatrix=new StringBuffer[mrow][mcol];
        for(int i=0;i<mrow;i++){
            for (int j=0;j<mcol;j++){
                dfaMatrix.accessMatrix[i][j]=new StringBuffer();
            }
        }


        //构造与Graph相对应的矩阵表
        //遍历边，得到横、纵坐标，存入结束状态
        for (int i = 0; i < dfaGraph.arcCount; i++) {
            int col=find_col_position(dfaGraph.arcCollection[i].access, dfaGraph.access);
            int row=find_row_position(dfaGraph.arcCollection[i].start,dfaMatrix.states);
            dfaMatrix.accessMatrix[row][col].append(dfaGraph.arcCollection[i].end.name);
        }
        //遍历accessMatrix,将空处填入^
        for (int i = 0; i < mrow; i++) {
            for (int j = 0; j < mcol; j++) {
                if(dfaMatrix.accessMatrix[i][j].length()==0){
                    dfaMatrix.accessMatrix[i][j].append('^');
                }
            }
        }
        return dfaMatrix;
    }

    /**
     * 得到终态集和非终态集
     * @param dfaMatrix
     * @return
     */
    public static ArrayList<Set<Character>> get_end_unend_set(DFAMatrix dfaMatrix){
        Set<Character> endGroup=new LinkedHashSet<>();
        for (int i = 0; i < dfaMatrix.endStateList.size(); i++) {
            endGroup.add(dfaMatrix.endStateList.get(i).name);
        }
        Set<Character> unendGroup=new LinkedHashSet<>();
        for (int i = 0; i < dfaMatrix.states.size(); i++) {
            if(!endGroup.contains(dfaMatrix.states.get(i).name)){
                unendGroup.add(dfaMatrix.states.get(i).name);
            }
        }
        ArrayList<Set<Character>> sets=new ArrayList<>();
        sets.add(endGroup);
        sets.add(unendGroup);
        return sets;
    }

    /**
     * 得到状态顶点分组
     * @param sets
     * @param dfaMatrix
     * @return
     */
    public static ArrayList<Set<Character>> dividedSet(ArrayList<Set<Character>> sets, DFAMatrix dfaMatrix){
        boolean flag=true;
        while (flag) {
            //Map记录每个顶点通过不同状态转换符去到的集合的编号
            Map<Character, ArrayList<Integer>> map = new HashMap<>();
            ArrayList<Set<Character>> isDividedSets = new ArrayList<>();
            //对分好的组进行遍历，判断是否可再分
            for (int i = 0; i < sets.size(); i++) {
                ArrayList<Character> arrayList = new ArrayList<>(sets.get(i));
                //得到每个状态 经状态转换符后 去到的状态集
                for (int j = 0; j < arrayList.size(); j++) {
                    ArrayList<Integer> setNum = new ArrayList<>();
                    for (int k = 0; k < dfaMatrix.access.size(); k++) {
                        int row = find_row_position(new State(arrayList.get(j)), dfaMatrix.states);
                        String s = dfaMatrix.accessMatrix[row][k].toString();
                        char c = s.charAt(0);
                        if(c!='^'){
                            //看这个终点属于哪个集合
                            for (int l = 0; l < sets.size(); l++) {
                                if (sets.get(l).contains(c)) {
                                    setNum.add(l);
                                }
                            }
                        }else {
                            setNum.add(-1);
                        }

                    }
                    map.put(arrayList.get(j), setNum);
                }
                //遍历该集合中的每一个状态，进行划分
                ArrayList<Set<Character>> tempSet = new ArrayList<>();
                for (int j = 0; j < arrayList.size(); j++) {
                    Set<Character> inThisSet = new LinkedHashSet<>();
                    Set<Character> notInThisSet = new LinkedHashSet<>();
                    for (int k = 0; k < arrayList.size(); k++) {
                        if (map.get(arrayList.get(j)).equals(map.get(arrayList.get(k)))) {
                            inThisSet.add(arrayList.get(k));
                        } else {
                            notInThisSet.add(arrayList.get(k));
                        }
                    }
                    tempSet.add(inThisSet);
                    tempSet.add(notInThisSet);
                }
                //对得到的划分集合进行去重
                for (int j = 0; j < tempSet.size(); j++) {
                    ArrayList<Character> temp1 = new ArrayList<>(tempSet.get(j));
                    temp1.sort(Comparator.naturalOrder());
                    String s1 = temp1.toString();
                    for (int k = j + 1; k < tempSet.size(); k++) {
                        ArrayList<Character> temp2 = new ArrayList<>(tempSet.get(k));
                        temp2.sort(Comparator.naturalOrder());
                        String s2 = temp2.toString();
                        if (s1.equals(s2)) {
                            tempSet.get(k).clear();
                        }
                    }
                }
                ArrayList<Set<Character>> newSet = new ArrayList<>();
                for (int j = 0; j < tempSet.size(); j++) {
                    if (!tempSet.get(j).isEmpty()) {
                        newSet.add(tempSet.get(j));
                    }
                }
                for (int j = 0; j < newSet.size(); j++) {
                    isDividedSets.add(newSet.get(j));
                }
                // System.out.println(isDividedSets);
                // System.out.println(sets);

            }
            //判断是否进行下一次循环
            if (isDividedSets.size() == sets.size()) {
                flag = false;
            } else {
                sets.clear();
                sets = isDividedSets;
            }
        }
        return sets;
    }

    /**
     * 对得到的化简的表重新命名，得到新的DFAMatrix
     * @param sets
     * @param dfaMatrix
     * @return
     */
    public static DFAMatrix reName(ArrayList<Set<Character>> sets,DFAMatrix dfaMatrix){
        StringBuffer[][] stringBuffer=new StringBuffer[sets.size()][dfaMatrix.access.size()];
        for (int i = 0; i < sets.size(); i++) {
            for (int j = 0; j < dfaMatrix.access.size(); j++) {
                stringBuffer[i][j]=new StringBuffer();
            }
        }
        char[] name=new char[26];
        for(int i=0;i<name.length;i++){
            name[i]=(char) (65+i);
        }

        Map<Character,ArrayList<Character>> map=new HashMap<>();
        ArrayList<State> newEndStateList=new ArrayList<>();
        State startState=new State();
        for (int i = 0; i < sets.size(); i++) {
            ArrayList<Character> characters=new ArrayList<>(sets.get(i));
            ArrayList<Character> whichSet=new ArrayList<>();
            char c=characters.get(0);
            int row=find_row_position(new State(c), dfaMatrix.states);
            for (int j = 0; j < dfaMatrix.access.size(); j++) {
                char ch=dfaMatrix.accessMatrix[row][j].charAt(0);
                if(ch!='^'){
                    for (int k = 0; k < sets.size(); k++) {
                        if(sets.get(k).contains(ch)){
                            whichSet.add(name[k]);
                            break;
                        }
                    }
                }else {
                    whichSet.add('^');
                }

                for (int k = 0; k < sets.size(); k++) {
                    //更新终态集
                    for (int l = 0; l < dfaMatrix.endStateList.size(); l++) {
                        if(sets.get(k).contains(dfaMatrix.endStateList.get(l).name)){
                            newEndStateList.add(new State(name[k]));
                            break;
                        }
                    }
                    //更新开始状态
                    if (sets.get(k).contains(dfaMatrix.startState.name)){
                        startState=new State(name[k]);
                    }
                }
            }
            map.put(name[i],whichSet);
        }
        List<State> states=new ArrayList<>();
        //遍历map，建立新的DFAMatrix
        for(Character c:map.keySet()){
            states.add(new State(c));
        }
        int arcCount=0;
        for (int i = 0; i < states.size(); i++) {
            for (int j = 0; j < dfaMatrix.access.size(); j++) {
                int row=find_row_position(states.get(i),states);
                char endState=map.get(states.get(i).name).get(j);
                if(endState!='^'){
                    arcCount++;
                }
                stringBuffer[row][j].append(endState);
            }
        }

        int stateCount=states.size();
        for (int i = 0; i < newEndStateList.size(); i++) {
            for (int j = i+1; j < newEndStateList.size() ; j++) {
                if (newEndStateList.get(i).name==newEndStateList.get(j).name){
                    newEndStateList.get(j).name='#';
                }
            }
        }
        ArrayList<State> endStateList=new ArrayList<>();
        for (int i = 0; i < newEndStateList.size(); i++) {
            if(newEndStateList.get(i).name!='#'){
                endStateList.add(newEndStateList.get(i));
            }
        }
        DFAMatrix newDFAMatrix=new DFAMatrix(states, dfaMatrix.access, arcCount,stateCount,startState,endStateList);
        newDFAMatrix.accessMatrix=stringBuffer;
        return newDFAMatrix;
    }

    /**
     * 得到最小DFAGraph
     * @param dfaMatrix
     * @return
     */
    public static DFAGraph DFAMatrix_to_DFAGraph(DFAMatrix dfaMatrix){
        DFAGraph dfaGraph=new DFAGraph();
        dfaGraph.arcCollection=new Arc[dfaMatrix.arcCount];
        dfaGraph.startState=dfaMatrix.startState;
        dfaGraph.endStateList=dfaMatrix.endStateList;
        dfaGraph.access= dfaMatrix.access;
        dfaGraph.arcCount=dfaMatrix.arcCount;
        int count=0;
        for (int j = 0; j < dfaMatrix.states.size(); j++) {
            for (int k = 0; k < dfaMatrix.access.size(); k++) {
                int row=find_row_position(dfaMatrix.states.get(j),dfaMatrix.states);
                State start=new State(dfaMatrix.states.get(j).name);
                Character access=dfaMatrix.access.get(k);
                State end=new State(dfaMatrix.accessMatrix[row][k].charAt(0));
                if(end.name!='^'){
                    Arc arc=new Arc(start,end,access);
                    dfaGraph.arcCollection[count++]=arc;
                }
            }
        }
        return dfaGraph;
    }

    public static DFAGraph DFA_minimize(DFAGraph dfaGraph){
        DFAGraph minDFA=new DFAGraph();

        //将图用状态转移矩阵表示
        DFAMatrix dfaMatrix=DFAGraph_to_DFAMatrix(dfaGraph);
        //得到终态集和非终态集
        ArrayList<Set<Character>> sets=get_end_unend_set(dfaMatrix);
        //得到最终划分好的集合
        sets=dividedSet(sets,dfaMatrix);
        //得到最小DFA的状态转移矩阵
        dfaMatrix=reName(sets,dfaMatrix);
        //状态转移矩阵变为图
        minDFA=DFAMatrix_to_DFAGraph(dfaMatrix);
        return minDFA;
    }
}

